#ifndef STX_ALGORITHM_PUSH_HEAP_HPP
#define STX_ALGORITHM_PUSH_HEAP_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/move.hpp>

namespace stx {

template <class Compare, class RandomAccessIterator>
inline void
push_heap_front(
    RandomAccessIterator first,
    RandomAccessIterator,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
    if (len > 1) {
        difference_type p = 0;
        RandomAccessIterator pp = first;
        difference_type c = 2;
        RandomAccessIterator cp = first + c;
        if (c == len || comp(*cp, *(cp - 1))) {
            --c;
            --cp;
        }
        if (comp(*pp, *cp)) {
            value_type t(stx::move(*pp));
            do {
                *pp = stx::move(*cp);
                pp = cp;
                p = c;
                c = (p + 1) * 2;
                if (c > len) {
                    break;
                }
                cp = first + c;
                if (c == len || comp(*cp, *(cp - 1))) {
                    --c;
                    --cp;
                }
            } while (comp(t, *cp));
            *pp = stx::move(t);
        }
    }
}

template <class Compare, class RandomAccessIterator>
inline void
push_heap_back(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
    if (len > 1) {
        len = (len - 2) / 2;
        RandomAccessIterator ptr = first + len;
        if (comp(*ptr, *--last)) {
            value_type t(stx::move(*last));
            do {
                *last = stx::move(*ptr);
                last = ptr;
                if (len == 0) {
                    break;
                }
                len = (len - 1) / 2;
                ptr = first + len;
            } while (comp(*ptr, t));
            *last = stx::move(t);
        }
    }
}

template <class RandomAccessIterator, class Compare>
inline void
push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    push_heap_back<comp_ref>(first, last, comp, last - first);
}

template <class RandomAccessIterator>
inline void
push_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    stx::push_heap(
        first,
        last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_PUSH_HEAP_HPP
